![]() ![]() ![]() |
Since iterators are a generalization of pointers, their semantics is a generalization of the semantics of pointers. Depending on the operations defined on them, there are five categories of iterators: input iterators, output iterators, forward iterators, bidirectional iterators and random access iterators. Forward iterators satisfy all the requirements of the input and output iterators and can be used whenever either kind is specified. Bidirectional iterators satisfy all the requirements of the forward iterators and can be used whenever a forward iterator is specified. Random access iterators satisfy all the requirements of bidirectional iterators and can be used whenever a bidirectional iterator is specified.
InputIterator
and OutputIterator
extends
the Iterator api interface.
For any iterator type there is an iterator value that points past the
last element of a corresponding container.
These values are called past-the-end values.
Values of the iterator for which the get()
and
put(Object)
is defined are called dereferenceable.
The library never assumes that past-the-end values are dereferenceable.
Iterators might also have singular values that are not associated
with any container. For example, after the declaration of an
uninitialized iterator x
(as with Iterator x;
),
x
should always be assumed to have a singular value.
Results of most expressions are undefined for singular values.
The only exception is an assignment of a non-singular value to an
iterator that holds a singular value.
In this case the singular value is overwritten the same way as any other value.
Dereferenceable and past-the-end values are always non-singular.
An iterator j
is called reachable from an
iterator i
if and only if there is a finite sequence of
applications of next()
to i
that makes
i.cmp(j)
return true.
If i
and j
refer to the same container,
then either j
is reachable from i
, or i
is reachable from j
, or both (i == j
).
Most of the library's algorithmic method that operate on data structures
have interfaces that use ranges.
A range is a pair of iterators that designate the beginning and end of
the computation. A range [i,i)
is an empty range; in general,
a range [i,j)
refers to the elements in the data structure
starting with the one pointed to by i
and up to but not including
the one pointed to by j
. Range [i,j)
is valid
if and only if j
is reachable from i
.
The result of the application of the algorithms in the library to
invalid ranges is undefined.
All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables for the iterators do not have a complexity column.
![]() ![]() ![]() |